
 public class ListNode {
  public var val: Int
  public var next: ListNode?
  public init() { self.val = 0; self.next = nil; }
  public init(_ val: Int) { self.val = val; self.next = nil; }
  public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }

 }


class Solution {
    /**
解法1 设定一个反向链表，然后匹配是否相等
*/
    func isPalindrome(_ head: ListNode?) -> Bool {
        var reverseNode = ListNode(0,nil)
        var node = head

        while node.next != nil{
            if reverseNode.next == nil{
                reverseNode.next = node
            }else {
                reverseNode.next = node
            }
          
        }
        


    }

/**
解法2 快慢双指针 
*/
    func isPalindrome(_ head: ListNode?) -> Bool {
        if head == nil  {return true}
        var size= 0

        var currNode = head

        while currNode!= nil{
            currNode = currNode!.next
            size+=1
        }

        var mid = size/2
        
        currNode = head
        var slowNode = head

        var index = 1

        while currNode != nil{
            if index > mid{
                if slowNode!.val != currNode!.val{
                    return false
                }
                 slowNode = slowNode!.next
            }
            currNode = currNode!.next
        }

    }


    /*
    解法3 转字符串、数组等
    */
    func isPalindrome(_ head: ListNode?) -> Bool {
        var str=""
        var reverseStr = ""

        var node = head
        while node != nil {
            str += String(node!.val)
            reverseStr = String(node!.val)+reverseStr

            node = node!.next
        }
        return str == reverseStr;
    }
}